﻿/*
 * 名称：程序设计语言-编译原理算法，移进-规约(Shift-Reduce)分析主程序
 * 制作者：WT
 * 创建时间：2012-10
 */
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using CompilerDLL.LexicalAnalysis;


namespace CompilerDLL.SyntaxAnalysis.Bottom_Up_Analysis
{
    public class Shift_Reduce_Analysis:BaseSyntaxParse 
    {

        #region 构造方法
        public Shift_Reduce_Analysis()
        {
            ModelProduction m1 = new ModelProduction();
            m1.Head = "E";
            m1.Body.Add("T");
            this.hashGrammarReverseProduction["T"] = m1;

            ModelProduction m2 = new ModelProduction();
            m2.Head = "E";
            m2.Body.Add("E");
            m2.Body.Add("+");
            m2.Body.Add("T");
            this.hashGrammarReverseProduction["E+T"] = m2;

            ModelProduction m3 = new ModelProduction();
            m3.Head = "T";
            m3.Body.Add("F");
            this.hashGrammarReverseProduction["F"] = m3;

            ModelProduction m4 = new ModelProduction();
            m4.Head = "T";
            m4.Body.Add("T");
            m4.Body.Add("*");
            m4.Body.Add("F");
            this.hashGrammarReverseProduction["T*F"] = m4;

            ModelProduction m5 = new ModelProduction();
            m5.Head = "F";
            m5.Body.Add("i");
            this.hashGrammarReverseProduction["i"] = m5;

            ModelProduction m6 = new ModelProduction();
            m6.Head = "F";
            m6.Body.Add("(");
            m6.Body.Add("E");
            m6.Body.Add(")");
            this.hashGrammarReverseProduction["(E)"] = m6;

            hashUnReducable["E*i+i"] = 1;

        }
        #endregion 

        #region 私有变量

        /// <summary>
        ///不可规约表，如果当前句型是不可规约的则标为1
        /// </summary>
        Hashtable hashUnReducable = new Hashtable();

        #endregion 

        #region 私有方法

        /// <summary>
        /// 标注层次
        /// </summary>
        /// <param name="currentTreeNode"></param>
        /// <param name="level"></param>
        private void NoteLevel(
            SyntaxTreeNode currentTreeNode,
            int level)
        {
            if (currentTreeNode.ChildNodes != null)
            {
                level++;
                int intChildNodes = currentTreeNode.ChildNodes.Count;

                for (int i = 0; i < intChildNodes; i++)
                {
                    
                    SyntaxTreeNode childNode = (SyntaxTreeNode)currentTreeNode.ChildNodes[i];
                    childNode.Level = level;
                    this.NoteLevel(childNode, level);

                }
            }
           

        }

        #region 记录每一个分析步的状态

        /// <summary>
        /// 记录每一个分析步的当前状态
        /// </summary>
        /// <param name="inputIndex">当前的输入单词的指针</param>
        /// <param name="currentStep">当前的执行步</param>
        ///  <param name="modelCurrentProduction">当前步所用的产生式</param>
        /// <param name="currentSyntaxTreeNode">当前语法树状态</param>
        /// <param name="isShiftOrReduce">当前操作状态,0为移进，1为规约</param>
        /// <returns>Model,保存每一次的当前分析状态</returns>
        private Model_Shift_Reduce_StepStatus RecordCurrentForecastAnalysisSteps(
            int inputIndex,
            int currentStep,
            ModelProduction modelCurrentProduction,
            SyntaxTreeNode currentSyntaxTree,
            int isShiftOrReduce)
        {
            Model_Shift_Reduce_StepStatus model_stepStatus =
                new Model_Shift_Reduce_StepStatus();
           
            #region (1).记录当前的执行步数。
            //(1).记录当前的执行步数。
            model_stepStatus.IntStep = currentStep;
            #endregion

            #region (2)记录当前的单词符号串
            for (int i = inputIndex; i < this.arrayTokens.Count; i++)
            {
                LexicalAnalysis.ModelTokenType modelCurrentToken =
                    (LexicalAnalysis.ModelTokenType)this.arrayTokens[i];
                model_stepStatus.StrCurrentTokens += modelCurrentToken.Lexem;

            }
            #endregion

            #region (3).当前步的产生式
            if (modelCurrentProduction == null)
            {
                model_stepStatus.StrCurrentProduction = "";
            }
            else
            {
                model_stepStatus.StrCurrentProduction +=
                    modelCurrentProduction.Head;
                model_stepStatus.StrCurrentProduction +=
                    "->";
                for (int i = 0; i < modelCurrentProduction.Body.Count; i++)
                {
                    model_stepStatus.StrCurrentProduction +=
                        (string)modelCurrentProduction.Body[i];

                }

            }
            #endregion

            #region (4).记录当前的栈中的符号状态
            //记录当前的栈状态
            Stack stackCurrent = (Stack)this.stackProcSymbols.Clone();
            int stackLength = stackCurrent.Count;
            for (int i = 0; i < stackLength; i++)
            {
                SyntaxTreeNode currentStackTreeNode=(SyntaxTreeNode) stackCurrent.Pop();

                model_stepStatus.StrStackProcSymbols =
                   currentStackTreeNode .NodeSymbol + model_stepStatus.StrStackProcSymbols;
            }
            #endregion

            #region (5).记录当前栈中的各子树的状态，并设立一个虚拟节点，用于标识是否已经分析完成
            stackCurrent = (Stack)this.stackProcSymbols.Clone();
            stackLength = stackCurrent.Count;
             Stack tempStack = new Stack();
            //调换顺序
            for (int i = 0; i < stackLength-1; i++)
            {
               
                tempStack.Push((SyntaxTreeNode )stackCurrent.Pop());
            }
            model_stepStatus.Current_Syntax_Tree.NodeSymbol = "自下而上分析，移进-规约（Shift-Reduce)算法";
            model_stepStatus.Current_Syntax_Tree.Level = 0;
            stackLength = tempStack.Count;
            for (int i = 0; i < stackLength; i++)
            {
                SyntaxTreeNode currentRootTreeNode = new SyntaxTreeNode();
                   currentRootTreeNode= (SyntaxTreeNode)tempStack.Pop();
                currentRootTreeNode.ParentNode = model_stepStatus.Current_Syntax_Tree;
                model_stepStatus.Current_Syntax_Tree.ChildNodes.Add(currentRootTreeNode);
            }
            this.NoteLevel(model_stepStatus.Current_Syntax_Tree, 0);
            this.syntaxTree = model_stepStatus.Current_Syntax_Tree;

            #endregion 

            #region (6).当前操作状态,0为移进，1为规约,-1为预备

            if (isShiftOrReduce ==0)
            {
                model_stepStatus.CurrentAction = "移进（Shift)";
            }
            if (isShiftOrReduce == 1)
            {
                model_stepStatus.CurrentAction = "规约（Reduce)";
            }
            if (isShiftOrReduce == 3)
            {
                model_stepStatus.CurrentAction = "预备";
            }
            #endregion
            string strOutput =
                currentStep.ToString()
                + "    " + model_stepStatus.StrStackProcSymbols
                + "    " + model_stepStatus.StrCurrentTokens
                + "    " + model_stepStatus.StrCurrentProduction
                +"    " + model_stepStatus.CurrentAction;

            Console.WriteLine(strOutput);
            return model_stepStatus;

        }
        #endregion

        #region 判断是否为从栈顶元素开始的句柄
        /// <summary>
        /// 判断是否为从栈顶元素开始的句柄
        /// </summary>
        /// <param name="stackTempProcSymbol"></param>
        /// <returns></returns>
        private string IsHandle(Stack stackTempProcSymbol)
        {
           
            //候选串
            string candidateHandle="";
           
            int intStackLength = stackTempProcSymbol.Count;

            //从栈底开始，求得最长的字符串
            for (int i = 0; i < intStackLength - 1; i++)
            {
                SyntaxTreeNode syntaxTreeNode = (SyntaxTreeNode)stackTempProcSymbol.Pop();
                candidateHandle = syntaxTreeNode.NodeSymbol + candidateHandle;
            }

            
            //如果不是句柄，继续循环，并去掉字符串的首符，直到形成句柄
            int intCandidateLength=candidateHandle.Length;
            for (int i = 0; i < intCandidateLength; i++)
            {
                if (this.hashGrammarReverseProduction[candidateHandle] != null)
                {

                    return candidateHandle;
                }
                else
                {
                    candidateHandle = candidateHandle.Substring(1, candidateHandle.Length - 1);
                   
                }
            }
            return candidateHandle;
          
        }
        #endregion

        #region 判断句柄是否可规约
        /// <summary>
        /// 先得到按当前的候选句柄得到的规约后的结果，并判断是否可规约，即当前候选句柄的合法性
        /// </summary>
        /// <param name="stackProcSymbol">符号栈</param>
        /// <param name="modelCurrentReductionProduction">当前候选句柄规约所依赖的产生式</param>
        /// <param name="intInputIndex">当前的单词串的输入指针</param>
        /// <returns>如果按当前句柄规约后的句型合法，则进行规约</returns>
        private bool isReducable(
            Stack stackProcSymbol,
            ModelProduction modelCurrentReductionProduction,
            int intInputIndex
            )
        {
            string reducedCandidateSentence = "";
            
            //(1)先得到符号栈中已经有的符号
            stackProcSymbol.Pop();
            int stackLength = stackProcSymbol.Count;
            for (int i = 0; i < stackLength-1; i++)
            {
                SyntaxTreeNode treeNode = (SyntaxTreeNode)stackProcSymbol.Pop();
                reducedCandidateSentence = treeNode.NodeSymbol + reducedCandidateSentence;
            }

            //(2)得到候选句柄规约后的符号
            reducedCandidateSentence = reducedCandidateSentence+modelCurrentReductionProduction.Head;

            //(3）得到输入串中剩余的符号 
            for (int i = intInputIndex; i < this.arrayTokens.Count-1; i++)
            {
                string indexedToken;

                CompilerDLL.LexicalAnalysis.ModelTokenType modelCurrentIndexedToken =
                    (CompilerDLL.LexicalAnalysis.ModelTokenType)this.arrayTokens[i];

                if ((modelCurrentIndexedToken.TokenType == 5) || (modelCurrentIndexedToken.TokenType == 1))
                {
                    indexedToken = "i";
                }
                else
                {
                    indexedToken = modelCurrentIndexedToken.Lexem;
                }

                reducedCandidateSentence = reducedCandidateSentence + indexedToken;
            }

            //如果按当前句柄规约后的句型不合法，则返回false
            if (hashUnReducable.Contains(reducedCandidateSentence))
            {

                return false;
            }
            else
            {
                return true;
            }
            
        }
        #endregion 

      
        #endregion

        #region 重写父类的方法，主程序
        /// <summary>
        ///  重写父类的方法
        /// </summary>
        /// <param name="arrayTokens">源程序输入串</param>
        /// <returns>返回解析结果</returns>
        public override ArrayList Syntax_Parse_Main(
            ArrayList arrayTokens,
            string strPara)
        {
            //候选句柄
            string candidateHandle;

            //当前的执行步，从0开始
            int intCurrentStep = 0;

            //在输入串后加“#”
            this.ModifyTheInputTokens(arrayTokens);

            //初始化符号栈
            SyntaxTreeNode syntaxInitTreeNode = new SyntaxTreeNode();
            syntaxInitTreeNode.NodeSymbol = "#";
            this.stackProcSymbols.Push(syntaxInitTreeNode);

            //flag为false时退出循环
            bool flag = true;

            //标志当前正在解析的单词
            int intInputIndex = 0;

            //当前指针所指向的字符
            ModelTokenType modelCurrentIndexedToken;

            //当前所用的用于进行规约的产生式
            ModelProduction modelCurrentReductionProduction;


            //clone为临时栈
            Stack stackTempProcSymbol = new Stack();

            this.arraySyntaxAnalysisSteps.Add(this.RecordCurrentForecastAnalysisSteps(intInputIndex, intCurrentStep, null, null, 3));

            while (flag)
            {

                //当前步+1
                intCurrentStep++;

                #region 用于判断是否为终止条件
                //用于判断是否为终止条件下的临时栈，并将判断条件放入stackTop="E#"
                stackTempProcSymbol = (Stack)this.stackProcSymbols.Clone();
                string stackTop = "";
                if (stackTempProcSymbol.Count > 1)
                {

                    SyntaxTreeNode syntaxTopSymbol = (SyntaxTreeNode)stackTempProcSymbol.Pop();
                    stackTop = syntaxTopSymbol.NodeSymbol;
                    syntaxTopSymbol = (SyntaxTreeNode)stackTempProcSymbol.Pop();
                    stackTop = stackTop + syntaxTopSymbol.NodeSymbol;
                }
              
                //判断是否已经指向输入串的“#”
                modelCurrentIndexedToken =
                    (ModelTokenType)this.arrayTokens[intInputIndex];
                #endregion 
               
                //如果"E#"和“#”同时满足，则退出循环
                if ((stackTop == "E#") && (modelCurrentIndexedToken.Lexem== "#"))
                {
                    flag = false;
                }
                else
                {
                    //从栈顶元素开始查找句柄，即可规约串
                    stackTempProcSymbol = (Stack)this.stackProcSymbols.Clone();
                    candidateHandle = this.IsHandle(stackTempProcSymbol);

                    #region 如果从栈顶元素开始的候选句柄不为空，则进行考虑进行“规约”，如果候选句柄合法，同时将新规约好的子树入栈
                    //如果从栈顶元素开始的候选句柄不为空，则进行考虑进行“规约”，如果候选句柄合法，同时将新规约好的子树入栈
                    if (candidateHandle != "")
                    {
                        //得到当前规约步，按当前候选句柄得到的规约结果
                        modelCurrentReductionProduction=new ModelProduction();
                        modelCurrentReductionProduction=(ModelProduction)this.hashGrammarReverseProduction[candidateHandle];

                        //判断按当前的候选句柄是否可以规约
                        //先得到按当前的候选句柄得到的规约后的结果，并判断是否可规约，即当前候选句柄的合法性
                        //如果合法则进行规约
                        #region 如果合法则进行规约

                        #region radio是否进行规约合法判断
                        bool reduceVerification=true;
                        if(strPara=="1")
                        {
                            reduceVerification=true && this.isReducable(
                            (Stack)this.stackProcSymbols.Clone(), 
                            modelCurrentReductionProduction, 
                            intInputIndex);

                        }
                        if (strPara == "0")
                        {
                            reduceVerification = true || this.isReducable(
                            (Stack)this.stackProcSymbols.Clone(),
                            modelCurrentReductionProduction,
                            intInputIndex);
                        }
                        #endregion

                        if (reduceVerification)
                        {
                            //添加新的规约后的父节点
                            string currrntRootSymbol = modelCurrentReductionProduction.Head;
                            SyntaxTreeNode subSyntaxTreeRootNode = new SyntaxTreeNode();
                            subSyntaxTreeRootNode.NodeSymbol = currrntRootSymbol;

                            //从符号栈中将句柄退栈，并利用tempStack重新排序，以方便生成自左向右的子树
                            Stack tempStack = new Stack();
                            for (int i = 0; i < candidateHandle.Length; i++)
                            {

                                tempStack.Push((SyntaxTreeNode)this.stackProcSymbols.Pop());
                            }

                            //从栈顶开始，将排序好的符号，作为新规约后的父节点的新的子树
                            for (int i = 0; i < candidateHandle.Length; i++)
                            {
                                SyntaxTreeNode subCurrentChildTreeNode = new SyntaxTreeNode();
                                   subCurrentChildTreeNode= (SyntaxTreeNode)tempStack.Pop();
                                subCurrentChildTreeNode.ParentNode = subSyntaxTreeRootNode;
                                subSyntaxTreeRootNode.ChildNodes.Add(subCurrentChildTreeNode);
                            }

                            //将新形成的规约后的子树入符号栈
                            this.stackProcSymbols.Push(subSyntaxTreeRootNode);

                            this.arraySyntaxAnalysisSteps.Add
                                (this.RecordCurrentForecastAnalysisSteps(intInputIndex, intCurrentStep, modelCurrentReductionProduction, null, 1));

                        }
                        #endregion

                        #region 否则，进行移进
                        else
                        {
                            SyntaxTreeNode subSyntaxTreeLeafNode = new SyntaxTreeNode();
                            subSyntaxTreeLeafNode.ChildNodes = null;
                            subSyntaxTreeLeafNode.IntCurrentStep = intCurrentStep;

                            //如果是标识符时，统一按i来索引
                            if ((modelCurrentIndexedToken.TokenType == 5) || (modelCurrentIndexedToken.TokenType == 1))
                            {
                                subSyntaxTreeLeafNode.NodeSymbol = "i";
                            }
                            else
                            {
                                subSyntaxTreeLeafNode.NodeSymbol = modelCurrentIndexedToken.Lexem;
                            }

                            this.stackProcSymbols.Push(subSyntaxTreeLeafNode);

                            intInputIndex++;

                            this.arraySyntaxAnalysisSteps.Add
                                (this.RecordCurrentForecastAnalysisSteps(intInputIndex, intCurrentStep, null, null, 0));

                        }
                        #endregion 




                    }
                    #endregion 

                    #region 否则，则进行“移进”，同时将新入栈的单词作为子树的叶子节点
                    
                    //否则，则进行“移进”，同时将新入栈的单词作为子树的叶子节点
                    else
                    {
                        SyntaxTreeNode subSyntaxTreeLeafNode = new SyntaxTreeNode();
                        subSyntaxTreeLeafNode.ChildNodes = null;
                        subSyntaxTreeLeafNode.IntCurrentStep = intCurrentStep; 

                         //如果是标识符时，统一按i来索引
                        if ((modelCurrentIndexedToken.TokenType == 5) || (modelCurrentIndexedToken.TokenType == 1))
                        {
                            subSyntaxTreeLeafNode.NodeSymbol = "i";
                        }
                        else
                        {
                            subSyntaxTreeLeafNode.NodeSymbol = modelCurrentIndexedToken.Lexem;
                        }

                        this.stackProcSymbols.Push(subSyntaxTreeLeafNode);

                        intInputIndex++;

                        this.arraySyntaxAnalysisSteps.Add
                            (this.RecordCurrentForecastAnalysisSteps(intInputIndex, intCurrentStep, null, null, 0));

                        
                   
                    }
                    #endregion 
                }
            }

            
            return this.arraySyntaxAnalysisSteps;
        }
        #endregion 

    }
}
